10380. LinkedList Середина

Задан связный список. Найдите его средний элемент.

Определение связного списка:

//Java

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

// C++

class ListNode

{

public:

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

Реализуйте функцию MiddleElement, которая взвращает указатель на средний элемент. Если список содержит n элементов, то его средним будет элемент с индексом .

// Java

ListNode MiddleElement (ListNode head)

// C, C++

ListNode* MiddleElement (ListNode *head)

Пример

Длина списка n = 5 нечетная. Функция MiddleElement должна вернуть указатель на вершину со значением 3 (средний элемент).

Длина списка n = 4 четная. Функция MiddleElement должна вернуть указатель на вершину со значением 2 (средний элемент).

РЕШЕНИЕ

связный список

Анализ алгоритма

Воспользуемся двумя указателями p и q, двигая их по принципу малого и большого шага. Сначала установим их на начало списка. Далее итеративно двигаем первый указатель p вперед на одну позицию по списку, а второй q – на две позиции. Останавливаемся, когда указатель q достигнет конца списка.

Реализация алгоритма

ListNode* MiddleElement(ListNode *head)

{

Устанавливаем указатели p и q на начало списка.

ListNode *p = head;

ListNode *q = head;

Пока за указателем q имеется хотя бы два элемента (быстрый указатель передвигается на два шага вперед), продолжаем цикл.

while (q->next && q->next->next)

{

p = p->next;

q = q->next->next;

}

Когда q дойдет до конца, p будет указывать на средний элемент. Возвращаем p.

return p;

}

Java реализация

ListNode MiddleElement(ListNode head)

{

ListNode p = head;

ListNode q = head;

while (q.next != null && q.next.next != null)

{

p = p.next;

q = q.next.next;

}

return p;

}